package datastructure.binarytree;

public class BST {
	
//Inner class
	private static class BSTNode{
		Comparable data;
		BSTNode left;
		BSTNode right;
		
		BSTNode(){}
		
		BSTNode(Comparable obj){
			data = obj;
		}
		BSTNode(Comparable obj, BSTNode leftChild, BSTNode rightChild){
			data = obj;
			left = leftChild;
			right = rightChild;
		}
		public String toString(){
			return data.toString();
		}
	}
	
	private BSTNode root;	//root node of the tree
	private int count;
	
//constructor
	public BST(){
		clear();
	}
//Modifiers
	public void clear(){
		root = null;
		count = 0;
	}
	
	public void insert(Comparable val){
		root = insert(root, val);
	}
	
	public void delete(Comparable val){
		root = delete(root, val);
	}
	
//Accessors
	public boolean isEmpty(){
		return root == null;
	}
	
	public int size(){
		return count;
	}
	public boolean contains(Comparable val){
		return search(root, val) != null;
	}
	
	private Object search(BSTNode ref, Comparable val) {
		if(ref == null)
			return null;
		else {
			int comp = ref.data.compareTo(val);
			if(comp == 0)
				return ref;
			else if(comp == -1)
				return search(ref.right, val);
			else
				return search(ref.left, val);
		}
	}
	private BSTNode delete(BSTNode ref, Comparable val) {
		if(ref == null)
			return null;
		int comp = ref.data.compareTo(val);
		if(comp < 0)
			ref.right = delete(ref.right, val);
		else if(comp > 0)
			ref.left = delete(ref.left, val);
		count--;
		return deleteTopNode(ref);
	}
	private BSTNode deleteTopNode(BSTNode ref) {
		if(ref.left == null)
			return ref.right;
		else if(ref.right == null)
			return ref.left;
		else{
			return moveRightNode(ref);
		}
	}
	private BSTNode moveRightNode(BSTNode ref){
		if(ref == null)
			return null;
		if(ref.left == null)
			return ref.right;
		
		return ref.right = moveRightNode(ref.right);
//		ref.right.left = ref.left;
			
		
	}
	private BSTNode insert(BSTNode ref, Comparable val) {
		if( ref == null){
			count++;
			return new BSTNode(val);
		}
		int comp = val.compareTo(ref.data);
		if(comp<0)
			ref.left = insert(ref.left, val);
		else
			ref.right = insert(ref.right, val);
		return ref;
	}
	
	//ʵ�ֽ�������ת��Ϊ����
	BSTNode createBackbone(BSTNode root){
		if(root == null)
			return root;
		if(root.right != null)
			root.right = createBackbone(root.right);
		if(root.left != null){
			BSTNode oldRoot = root;
			BSTNode ref = root = createBackbone(root.left);
			oldRoot.left = null;
			while(root.right != null)
				ref = ref.right;
			ref.right = oldRoot;
		}
		return root;
	}
	
	//������ת����ƽ�������
	BSTNode createTree(BSTNode root, int n){
		if(n>2){
			int m = (n-1)/2;
			BSTNode oldRoot = root;
			BSTNode ref = root;
			for(int i=0;i<m;i++){
				ref = ref.right;
			}
			root = ref.right;
			ref.right = null;
			ref.left = createTree(oldRoot, m);
			ref.right = createTree(root,n-m-1);
		
		}
		return root;
	}
	
}
